package lc2;

import org.junit.Test;

public class Ex28 {

    class Solution {
        public int strStr(String haystack, String needle) {
            int[] next = getNextArray(needle);
            char[] hs = haystack.toCharArray(), ns = needle.toCharArray();
            int m = hs.length, n = ns.length;
            //s和p的指针
            int i = 0, j = 0;
            while (i < m && j < n) {
                if (hs[i] == ns[j]) {
                    i++;
                    j++;
                } else if (next[j] != -1) {
                    //移动j指针，用更短的公共前后缀后一个位置匹配
                    j = next[j];
                } else {
                    i++;
                    // j = 0; //若next[j] == -1，可以直接得到j=0
                }
            }
            //j没有越界，则说明匹配失败
            return j == n ? i - j : -1;
        }

        private int[] getNextArray(String needle) {
            char[] p = needle.toCharArray();
            int n = p.length;
            int[] next = new int[n];
            //标记为结束边界
            next[0] = -1;
            int i = 2;
            //记录前一个位置的最长公共前后缀
            int lastMaxPrefixLength = 0;
            while (i < n) {
                if (p[lastMaxPrefixLength] == p[i - 1]) {
                    /**
                     * 做了三件事：
                     * 1. 求解完了i位置的最长公共前后缀t = lastMaxPrefixLength + 1，使用next数组记录；
                     * 2. 将i自增1，表示下轮求解下个位置的最长公共前后缀；
                     * 3. lastMaxPrefixLength更新为i的最长公共前后缀，留给i + 1位置使用
                     */
                    next[i++] = ++lastMaxPrefixLength;
                } else if (lastMaxPrefixLength > 0) {
                    //p[0, i - 1]还有更短的公共前后缀可供作为跳板，就看p[i - 1]是否争气了
                    lastMaxPrefixLength = next[lastMaxPrefixLength];
                } else {
                    //若lastMaxPrefixLength == 0，则next[lastMaxPrefixLength] = -1, 会导致下轮循环数组越界
                    //而且这个位置本身就没有求next的必要, 因为在分支1已经考虑到了p[0]和p[i - 1]的比较了，到了这里说明连1都得不到
                    next[i++] = 0;
                }
            }
            return next;
        }

    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.strStr("hello","ll"));        
    }
    
}
